﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;

namespace QQ.InterviewQuestions.Array
{
    internal class FindMissingInteger
    {
        private const int bits = 20;
        private int[] array;

        public FindMissingInteger()
        {
            if (!File.Exists("numbers.txt"))
            {
                StreamWriter f = new StreamWriter("numbers.txt",false);
                using (f)
                {
                    QQ.InterviewQuestions.RandomShuffle.RandomShuffle o = new QQ.InterviewQuestions.RandomShuffle.RandomShuffle((int)Math.Pow(2, bits));
                    array = o.Execute();
                    for (int i = 0; i < array.Length; i++)
                    {
                        if (i != 5)
                        {
                            f.WriteLine(array[i]);
                        }
                    }
                }
            }
            else
            {
                int len = ((int)Math.Pow(2, bits)) - 1;
                array = new int[len];
                int i = 0;

                StreamReader f = new StreamReader("numbers.txt");
                using(f)
                {
                    while (! f.EndOfStream)
                    {
                        array[i] = int.Parse(f.ReadLine());
                        i++;
                    }
                }
            }
        }

        public int Find()
        {
            int n = 0;
            int[,] b = new int[2, 32];


            for (int i = 0; i < array.Length; i++)
            {
                n = array[i];
                for (int j = 0; j < bits; j++)
                {
                    int shifted = n >> j;
                    int bit = shifted % 2;
                    b[bit, j]++;
                }
            }
            
            int missing = 0;
            for (int i = bits - 1; i > -1; i--)
            {
                if (b[0, i] > b[1, i])
                    missing++;

                if (i != 0)
                {
                     missing = (missing << 1);
                }
            }

            return missing;
        }
    }
}
